home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.09 Sep 96 / Prog. Challenge / ConnectMove.cp next >
Encoding:
Text File  |  1996-07-09  |  13.7 KB  |  565 lines  |  [TEXT/R*ch]

  1. /*
  2.   1 July 1996.
  3.   Submission to MacTech Programmer's challenge for July-96.
  4.   Copyright 1996, Ernst Munter, Kanata, ON, Canada.
  5.  
  6.        "Connect IV"
  7.  
  8.   The challenge is to write code for a well-known game that will
  9.   compete against other entries, as well as against the clock.
  10.   The game board consists of an NxM array into which two players
  11.   alternate inserting pieces. Pieces are inserted into the top of
  12.   a column in the vertically oriented board, so that they drop
  13.   into the lowest unoccupied cell of that column. The objective is
  14.   to be the first player to arrange 4 or more pieces into a
  15.   vertical, horizontal, or diagonal line.
  16.  
  17. Solution
  18. --------
  19.   My solution is based on an unsophisticated look-ahead scheme.
  20.   We search, depth first, up to a maximum depth, to find the move
  21.   which will give the highest board score.  Dummy moves are executed
  22.   alternatingly by the 2 players, in a recursive function.
  23.  
  24.   At each recursion level, the board score accumulated at the
  25.   deeper levels is subtracted from the value of the move
  26.   contemplated at this level.
  27.  
  28.   In a full look-ahead to depth N, and with a board width of
  29.   C columns, we would have C^N moves to examine.
  30.  
  31.   Two techniques are combined to reduce the number of moves to
  32.   be examined:
  33.  
  34.   At each level, the search can stop if a certain threshold
  35.   is exceeded or a winning (losing) position is reached.
  36.   Exceeding the threshold would mean that the calling level
  37.   could not gain a better score, given its best score to
  38.   this point.
  39.  
  40.   In order to be able to stop searching (prune the tree),
  41.   we would like to start with moves which give the better
  42.   scores, i.e. rather than go from left to right across
  43.   the board, we start at the position of the last move and
  44.   go alternatingly left and right of that point.  This
  45.   tackles the active area of the board first where it is
  46.   more likely to find the best move.
  47.  
  48. Data Representation
  49. -------------------
  50.   The scoring relies entirely on a simple representation of
  51.   the state of the board.
  52.  
  53.   The board is visualized as covered with potential lines
  54.   (horizontal, vertical, diagonal) of 4 adjacent fields.
  55.   Each such line is called a "quad".
  56.  
  57.   A given field is associated with at least 3 (corner fields)
  58.   and at most 16 such quads (in the center of a large board).
  59.  
  60.   Each quad can have a state (empty, owned by player 1, owned
  61.   by player 2, or spoiled).  The spoiled state implies this
  62.   quad contains pieces from both players, and can no longer
  63.   be a winning quad.
  64.  
  65.   In addition, a non-empty quad has a value, depending on
  66.   how many player pieces it contains.
  67.  
  68.   I have arbitrarily set these values as follows:
  69.   empty               0
  70.   1 piece           1
  71.   2 pieces          16
  72.   3 pieces         256
  73.   4 pieces        4096
  74.  
  75.   The value of a placing a piece in a given field, is calculated
  76.   as the sum of the values of all quads associated with this
  77.   field.
  78.  
  79.   To simplify the book keeping, each field has an associated
  80.   data structure which points to all relevant quads.
  81.  
  82.   The Field structure also provides local stack space to hold
  83.   the previous values of its quads while a move is explored.
  84.  
  85.   A recognized weakness of this approach is that it treats
  86.   all quads equally, and does not recognize gravity, that is
  87.   the need to fill columns from the bottom.  This effect
  88.   can shadow otherwise good candidates from ever winning.
  89.   I had no time left to include this consideration in the
  90.   board scoring.
  91.  
  92. Running Time
  93. ------------
  94.   The depth of the tree dramatically affects the time to
  95.   compute a move, as does the width of the board.
  96.  
  97.   A few minor techniques are used to improve running time.
  98.  
  99.   After each move, all spoiled quads are removed from their
  100.   field references.
  101.  
  102.   All full columns are excluded from the move list.
  103.  
  104.   Empty columns "far away" from the action are also excluded.
  105.  
  106.   The MAGIC_NR constant can be used to adjust the speed
  107.   of the program.  A higher value increases the search
  108.   depth and the running time. 
  109.   
  110.   I set MAGIC_NR to 17 for acceptable all-round performance
  111.   on my computer.
  112.  
  113. Assumptions
  114. -----------
  115.   At least 7 columns are assumed.
  116.   The calling program should check for wins;
  117.   it is assumed that this function is not called
  118.   if the opponent has already won.
  119.  
  120.   A move value of -1 is returned when errors are
  121.   detected, e.g when there are no free fields left.
  122.  
  123.   This program does not include a randomizer since
  124.   it is assumed it will play only a few times against
  125.   computer opponents who, we hope will not be able
  126.   to take advantage of this.
  127.  
  128.   In a version to be played by humans, one would
  129.   randomly choose between equally good moves to
  130.   make it more interesting.
  131.  
  132. Note on style
  133. -------------
  134.   This program is basically a C program in spirit,
  135.   but using C++ structs for convenience in accessing
  136.   dynamic data.
  137.  
  138.   No inheritance, operator overloading or the like.
  139.  
  140.   All simple functions are listed inline, as part of the
  141.   class.  The implementations of functions with loops
  142.   are listed separately, following the struct declaration.
  143. */
  144.  
  145. #include <stdlib.h>
  146. //#include "viervier.h"
  147.  
  148. #define maxRow 63
  149. #define maxCol 64
  150.  
  151. #define maxQuad (((maxRow-3)*maxCol)+            \
  152.     ((maxCol-3)*maxRow)+(maxRow-3)*(maxCol-3)*2)
  153. #define empty          0
  154. #define self          1
  155. #define opponent     2
  156. #define spoiled      3
  157.  
  158. #define OTHER_PLAYER (3-player)
  159. #define WIN          4096
  160. #define MAX_MOVES    9
  161.  
  162. /*** This seems to work for me here, but please adjust
  163.      MAGIC_NR downward if program seems too slow *******/
  164. #define MAGIC_NR     17
  165.  
  166. struct Quad {
  167.   short status;                //who owns quad
  168.   short value;              //16 ^ (n-1);
  169.  
  170.   int     Update(int currentPlayer){
  171.     if (status==empty) {
  172.       status=(short)currentPlayer;
  173.       value=1;
  174.       return value;
  175.     }
  176.     if (status==currentPlayer) {
  177.       value <<= 4;              //higher value
  178.       return value;
  179.     }
  180.     if (status != spoiled) {        //other player
  181.       status=spoiled;
  182.       return value;            //plus for us
  183.     }
  184.     return 0;                //already spoiled
  185.   }
  186. };
  187. typedef struct Quad Quad;
  188.  
  189. struct Field {
  190.   Quad* quadRef[16];       //pointers to intersecting quads
  191.   Quad  savedState[16]; //stack to save quads before move
  192.  
  193.   void    AddQuad(Quad* qp);
  194.   void  SaveState();
  195.   void    RestoreState();
  196.   int    MakeMove(int currentPlayer);
  197.   void     Rationalize();
  198.   int    IsEmpty(){
  199.     if (quadRef[0]->status) return 0;
  200.     return 1;
  201.   }
  202. };
  203. typedef struct Field Field;
  204.  
  205. void Field::AddQuad(Quad* qp) {    //adds qp to list of quads
  206. int k;
  207.   for (k=0;k<16;k++) {
  208.     if (0==quadRef[k]) {
  209.       quadRef[k]=qp;
  210.       break;
  211.     }
  212.   }
  213. }
  214.  
  215. void Field::SaveState() {       //save all quads on stack
  216. Quad*     qp;
  217. Quad**     qh=quadRef;
  218. Quad*   savePtr=savedState;
  219. int     k;
  220.   for (k=0;k<16;k++) {
  221.     if (0 == (qp=*qh++)) break;
  222.     *savePtr++=*qp;
  223.   }
  224. }
  225.  
  226. void Field::RestoreState() {    //restore quads from stack
  227. Quad*     qp;
  228. Quad**     qh=quadRef;
  229. Quad*   savePtr=savedState;
  230. int     k;
  231.   for (k=0;k<16;k++) {
  232.     if (0 == (qp=*qh++)) break;
  233.     *qp=*savePtr++;
  234.   }
  235. }
  236.  
  237. int Field::MakeMove(int currentPlayer) {
  238. long     sum=0;
  239. long     val;
  240. Quad*     qp;
  241. Quad**     qh=quadRef;             //move=update all quads
  242.                 //return value of move
  243. int     k;
  244.   for (k=0;k<16;k++) {
  245.     if (0 == (qp=*qh++)) break;
  246.     val=qp->Update(currentPlayer);
  247.     if (val>=WIN) {
  248.       return WIN;
  249.     }
  250.     sum+=val;
  251.   }
  252.   return sum;
  253. }
  254.  
  255. void  Field::Rationalize() {
  256. int     i=0;
  257. int     k;
  258. int    nq=0;                   //remove all spoiled quads
  259.  
  260. //find number of non-0 quad refs
  261.   for (k=0;k<16;k++) {
  262.     if (quadRef[nq]) nq++;
  263.     else break;
  264.   }
  265.  
  266. //scan quad refs for spoiled quads, and remove
  267.   while(i<nq) {
  268.     Quad* qp=quadRef[i];
  269.     if (qp->status==spoiled) {
  270.       nq--;
  271.       if (i<nq)
  272.     quadRef[i]=quadRef[nq];
  273.       quadRef[nq]=0;
  274.     }
  275.     i++;
  276.   }
  277. }
  278.  
  279. struct PrivateData {
  280.   int     nextMove;        //next real move to do
  281.   int     numCols;        //number of columns
  282.   int     numRows;        //number of rows
  283.   int     numFree;        //number of fields free
  284.   int     level;            //recursion depth
  285.   int     numMoves;        //number of moves in move list
  286.   Field* endOfBoard;        //sentinel pointer
  287.   int     numHistory;        //move counter
  288.   int     history[maxCol*maxRow];//move history
  289.   int     moveList[maxCol];    //list of columns
  290.   Field* nextField[maxCol];    //next free field in column
  291.   Field     board[maxCol*maxRow];    //array of all fields
  292.   Quad     quadSet[maxQuad];    //array of all quads
  293.  
  294.   void    Initialize(long nCols,long nRows);
  295.   void    FirstMove() {nextMove = numCols >> 1;}
  296.   void    MakeMoveList(int move);
  297.   int     BestMove(int level,int player,int threshold);
  298.   void  Rationalize(int move);
  299.   int    CannedMove();
  300.   void  RecordMove(int move) {
  301.     if (numHistory==0)
  302.       history[numHistory++]=move;
  303.     else history[numHistory++]=move-history[0];
  304.   }
  305.   void     AdjustLevel() {
  306.     level=MAGIC_NR - numMoves;
  307.     if (numMoves<=7) level--;
  308.     if (level>=numFree) level=numFree-1;
  309.   }
  310.   int    UpdateBoard(int move,int player) {
  311.     Field* fp=nextField[move];
  312.     long score=fp->MakeMove(player);
  313.     nextField[move]=fp+numCols;
  314.     Rationalize(move);
  315.     numFree--;
  316.     return score;
  317.   }
  318. };
  319. typedef struct PrivateData PrivateData;
  320.  
  321. /*
  322. field numbering example (6*7)
  323.  
  324. 35 36 37 38 39 40 41   5  |
  325.               |
  326. 28 29 30 31 32 33 34   4
  327.               r
  328. 21 22 23 24 25 26 27   3  o
  329.               w
  330. 14 15 16 17 18 19 20   2  s
  331.  
  332.  7  8  9 10 11 12 13   1  |
  333.               |
  334.  0  1  2  3  4  5  6   0  |
  335.    --  columns --
  336. */
  337. void PrivateData::Initialize(long nCols,long nRows){
  338. int        col,row;
  339. Field*         field;
  340. Quad*        qp;
  341.  
  342.   numCols=nCols;
  343.   numRows=nRows;
  344.   numFree = nCols*nRows;
  345.  
  346.   endOfBoard=board+numFree;
  347.  
  348.   field=board;
  349.   for (col=0;col<nCols;col++)
  350.     nextField[col]=field++;
  351.  
  352.   field=board;
  353.   qp=quadSet;
  354.   for (row=0;row<nRows;row++) {        //set up quad references
  355.     for (col=0;col<nCols;col++) {
  356.       int direction,delta;
  357.       for (direction=0;direction<4;direction++) {
  358.                     //right, up-right, up, up-left
  359.  
  360.     switch (direction) {
  361.                     //eliminate all that dont fit
  362. case 0: if (col>=nCols-3) continue;break;
  363. case 1: if (col>=nCols-3) continue;
  364. case 2: if (row>=nRows-3) continue;break;
  365. case 3: if ((row>=nRows-3) || (col<3)) continue;
  366.     }
  367.  
  368.     for (delta=0;delta<4;delta++) {
  369.       Field* fp;
  370.       switch (direction) {
  371. case 0: fp=field+row*nCols+(col+delta);break;
  372. case 1: fp=field+(row+delta)*nCols+(col+delta);break;
  373. case 2: fp=field+(row+delta)*nCols+col;break;
  374. case 3: fp=field+(row+delta)*numCols+(col-delta);break;
  375.       }
  376.       fp->AddQuad(qp);
  377.     }
  378.     qp++;
  379.       }
  380.     }
  381.   }
  382. }
  383.  
  384. void  PrivateData::Rationalize(int move) {
  385.  
  386. //remove spoiled quads from all free fields in
  387. //the vicinity of a recent move
  388.  
  389. int i=move-3,j=move+4;
  390.   if (i<0) i=0;
  391.   if (j>numCols) j=numCols;
  392.   for (;i<j;i++) {
  393.     Field* fp=nextField[i];
  394.     while (fp<endOfBoard) {
  395.       fp->Rationalize();
  396.       fp+=numCols;
  397.     }
  398.   }
  399. }
  400.  
  401. void PrivateData::MakeMoveList(int move) {
  402. int     m=move;
  403. int    n=0;
  404. int    k=0;
  405.  
  406. //build the move sequence, starting from the center
  407. //out to the limits while skipping full columns.
  408.  
  409.   do {
  410.     if (nextField[m]<endOfBoard) moveList[n++]=m;
  411.     if (n>=MAX_MOVES) goto done;
  412.     k++;
  413.     if (0>(m=m-k)) goto go_right;
  414.     if (nextField[m]<endOfBoard) moveList[n++]=m;
  415.     if (n>=MAX_MOVES) goto done;
  416.     k++;
  417.     if (numCols<=(m=m+k)) goto go_left;
  418.   } while(1);
  419.  
  420. go_left:
  421.   if (0>(m=m-k-1)) goto done;
  422.   do {
  423.     if (nextField[m]<endOfBoard) moveList[n++]=m;
  424.     if (n>=MAX_MOVES) goto done;
  425.     m--;
  426.   } while(m>=0);
  427.   goto done;
  428.  
  429. go_right:
  430.   if (numCols<=(m=m+k+1)) goto done;
  431.   do {
  432.     if (nextField[m]<endOfBoard) moveList[n++]=m;
  433.     if (n>=MAX_MOVES) goto done;
  434.     m++;
  435.   } while(m<numCols);
  436.  
  437. done:
  438.   numMoves=n;
  439. }
  440.  
  441. int PrivateData::CannedMove() {
  442. #define H0 (history[0])
  443.   switch (numHistory) {
  444. case 1: if (H0>=3) return H0;
  445.     if (H0+3<numCols) return H0;
  446.     return numCols/2;
  447. case 2: switch (history[1]) {
  448.     case 0:return H0;
  449.     case 1:if (H0>=3) return H0-3;
  450.            else return H0;
  451.     case -1:if (numCols-H0>3) return H0+3;
  452.            else return H0;
  453.     case 2:case -2:return H0;
  454.     case 3:if (H0>=1) return H0-1;
  455.            else return H0-1;
  456.     case -3:if (numCols-H0>1) return H0+1;
  457.            else return H0+1;
  458.     default:if (H0>=2) return H0-1;
  459.            else return H0+3;
  460.     }
  461. case 3: if (history[1]==0) {
  462.       if (history[2]>=0) return H0-1;
  463.       if (history[2]<0) {
  464.         if (H0+1<numCols) return H0+1;
  465.       }
  466.     }
  467.   }
  468.   return -1;
  469. }
  470.  
  471. int PrivateData::BestMove(int level,int player,int threshold) {
  472. int     i;
  473. int    bestMove=-1;
  474. int    moveValue;
  475. int     score;
  476. int     bestV=-0x4000L;
  477.  
  478. //this routine is called recursively to return the value
  479. //of the best move.  The class variable "nextMove" holds
  480. //the column number for the "best" move.
  481.  
  482.   for (i=0;i<numMoves;i++) {
  483.     int m=moveList[i];        //work from list
  484.     Field* fp=nextField[m];
  485.     if (fp < endOfBoard) {    //else column is full
  486.       fp->SaveState();
  487.       nextField[m]+=numCols;
  488.       moveValue = fp->MakeMove(player);
  489.  
  490.       if (moveValue>=WIN) {    //win here: return right away
  491.     nextField[m]=fp;
  492.     fp->RestoreState();
  493.     nextMove=m;
  494.     return WIN*2;
  495.       }
  496.  
  497.       if (level) {        //descend to next level
  498.  
  499.     score=BestMove(level-1,OTHER_PLAYER,moveValue-bestV);
  500.     if (score>=WIN) {
  501.       moveValue=-score+1024;//bias for depth
  502.       goto skip;
  503.     }
  504.     moveValue -= score;    //and accumulate score
  505.       }
  506.  
  507.       if (moveValue>=threshold) {
  508.                 //no need to search further
  509.     nextField[m]=fp;
  510.     fp->RestoreState();
  511.     nextMove=m;
  512.     return moveValue;
  513.       }
  514. skip:
  515.       if (moveValue>bestV) {    //keep track of best so far
  516.     bestV=moveValue;
  517.     bestMove=m;
  518.       }
  519.  
  520.       nextField[m]=fp;
  521.       fp->RestoreState();
  522.     }
  523.   }
  524.   nextMove=bestMove;
  525.   return bestV;
  526. }
  527.  
  528. long ConnectMove4 (
  529.     long numCols,
  530.     long numRows,
  531.     void *privStorage,
  532.     long prevMove,
  533.     Boolean newGame,
  534.     Boolean *victory) {
  535.  
  536. PrivateData* PD=(PrivateData*)privStorage;
  537.  
  538.   if (newGame) {        //initialize on first call
  539.     PD->Initialize(numCols,numRows);
  540.     if (prevMove==-1) {
  541.       PD->FirstMove();         //standard first move
  542.       goto finish;
  543.     }
  544.   }
  545.  
  546.  
  547.   PD->UpdateBoard(prevMove,2);
  548.   PD->RecordMove(prevMove);
  549.  
  550.   if (PD->numFree<=0) return -1;    //the board is full
  551.  
  552.   if ((PD->nextMove=PD->CannedMove())<0) {
  553.  
  554.     PD->MakeMoveList(prevMove);
  555.  
  556.     PD->AdjustLevel();
  557.  
  558.     PD->BestMove(PD->level,1,WIN);
  559.   }
  560. finish:
  561.   *victory=(WIN<=PD->UpdateBoard(PD->nextMove,1));
  562.   PD->RecordMove(PD->nextMove);
  563.   return PD->nextMove;
  564. }
  565.